package hot;

import java.lang.reflect.Array;
import java.util.Arrays;

public class sanyi {

//    https://leetcode.cn/problems/next-permutation/submissions/677549789/?envType=study-plan-v2&envId=top-100-liked
        public static void nextPermutation(int[] nums) {
            //先从右往左找到第一个变小的数字
            int i=nums.length-2;
            while(i>=0&&nums[i]>=nums[i+1]){
                i--;
            }
            //走到这里就说明找到了
            if(i>=0){
                //交换数字
                //在[j,nums.length-1]从后往前找打第一个大于nums[i]的
                int j=nums.length-1;
                while(nums[j]<=nums[i]&&j>i){
                    j--;
                }
                swap(nums,i,j);
            }
            reverse(nums,i+1,nums.length-1);

        }
        public static void swap(int[] nums,int i,int j){
            int tmp=nums[i];
            nums[i]=nums[j];
            nums[j]=tmp;
        }
        public static void reverse(int[] nums,int start,int end){
            while(start<=end){
                swap(nums,start,end);
                start++;
                end--;
            }
        }

    public static void main(String[] args) {
        int[] nums={5,1,1};
        nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }

    }

